namespace LineIntersaction{
    //判断线段是否相交
    struct E{
        int x,y;
        E operator-(const E& t)const{
            return {x-t.x,y-t.y};
        }
    }w[5];
    int n=4;
    
    int cross(E a,E b){
        return a.x*b.y-a.y*b.x;
    }
    
    int dot(E a,E b){
        return a.x*b.x+a.y*b.y;
    }
    
    int sign(int x){
        if(x>0)return 1;
        if(x<0)return -1;
        return 0;
    }
    
    bool onseg(E a,E b,E c){
        if(cross(c-a,b-a)!=0)return 0;
        if(dot(c-a,b-a)>=0&&dot(c-a,b-a)<=dot(b-a,b-a))return 1;
        return 0;
    }
    
    bool get_line_instersaction(E a,E b,E c,E d){
        int f1=sign(cross(a-c,d-c))*sign(cross(b-c,d-c));
        int f2=sign(cross(c-a,b-a))*sign(cross(d-a,b-a));
        if(f1<0&&f2<0)return 1;
        if(f1>0||f2>0)return 0;
        if(onseg(a,b,c))return 1;
        if(onseg(a,b,d))return 1;
        if(onseg(c,d,a))return 1;
        if(onseg(c,d,b))return 1;
        return 0;
    }
}